By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 31, Issue 6, pp. 1663-1958

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model

Alexander Russell, Michael Saks, and David Zuckerman

pp. 1645-1662

BibTeX  Abstract Full Text:  PDF

Hardness of Approximate Hypergraph Coloring

Venkatesan Guruswami, Johan Hastad, and Madhu Sudan

pp. 1663-1686

BibTeX  Abstract Full Text:  PDF

Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions

Hsien-Kuei Hwang and Ralph Neininger

pp. 1687-1722

BibTeX  Abstract Full Text:  PDF

Are Bitvectors Optimal?

H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh

pp. 1723-1744

BibTeX  Abstract Full Text:  PDF

On the Boundary Complexity of the Union of Fat Triangles

János Pach and Gábor Tardos

pp. 1745-1760

BibTeX  Abstract Full Text:  PDF

Approximate String Matching: A Simpler Faster Algorithm

Richard Cole and Ramesh Hariharan

pp. 1761-1782

BibTeX  Abstract Full Text:  PDF

A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees

J. Könemann and R. Ravi

pp. 1783-1793

BibTeX  Abstract Full Text:  PDF

Maintaining Stream Statistics over Sliding Windows

Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani

pp. 1794-1813

BibTeX  Abstract Full Text:  PDF

Curvature-Constrained Shortest Paths in a Convex Polygon

Pankaj K. Agarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, and Sue Whitesides

pp. 1814-1851

BibTeX  Abstract Full Text:  PDF

Parallel Integer Sorting Is More Efficient Than Parallel Comparison Sorting on Exclusive Write PRAMs

Yijie Han and Xiaojun Shen

pp. 1852-1878

BibTeX  Abstract Full Text:  PDF

A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest

Seth Pettie and Vijaya Ramachandran

pp. 1879-1895

BibTeX  Abstract Full Text:  PDF

Lower Bounds for Lucas Chains

Martin Kutz

pp. 1896-1908

BibTeX  Abstract Full Text:  PDF

Simple Learning Algorithms for Decision Trees and Multivariate Polynomials

Nader H. Bshouty and Yishay Mansour

pp. 1909-1925

BibTeX  Abstract Full Text:  PDF

A Deterministic Polynomial-Time Algorithm for Heilbronn's Problem in Three Dimensions

Hanno Lefmann and Niels Schmitt

pp. 1926-1947

BibTeX  Abstract Full Text:  PDF

The Minimization Problem for Boolean Formulas

Edith Hemaspaandra and Gerd Wechsung

pp. 1948-1958

BibTeX  Abstract Full Text:  PDF